#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include "map_file.h"
#include "mergesort_inversion_vector.h"

FILE *get_output(char *infilename, char **outfilename, int mode);

uint32_t *compute_mtf(uint32_t *seq, uint32_t *input_len, uint32_t num_syms);
uint32_t *compute_dc(uint32_t *seq, uint32_t *input_len, uint32_t num_syms);

extern int optind;

enum {
	MODE_MTF, MODE_DC
};

void usage(const char *this_prog)
{
	fprintf(stderr, "Usage: %s <intsequencefile> [-m|-d] [-s <alphabet_size>] [<output.mtf|dc>]\n", this_prog);
	fprintf(stderr, "Input and output are 32-bit integers\n");
	fprintf(stderr, "  -m: Compute Move-to-Front (default)\n");
	fprintf(stderr, "  -d: Compute Distance Coding\n");
	exit(1);
}

int main(int argc, char *argv[])
{
	int i;
	uint32_t num_syms = 0;
	int mode = MODE_MTF;

	int opt;
	while ((opt = getopt(argc, argv, "dms:")) != -1) {
		switch (opt) {
		case 'd':
			mode = MODE_DC;
			break;
		case 'm':
			mode = MODE_MTF;
			break;
		case 's':
			num_syms = atoi(optarg);
			break;
		default: /* '?' */
			usage(argv[0]);
		}
	}

	if(optind == argc) {
		usage(argv[0]);
	}

	char *infilename = argv[optind++];
	ptr_range inmap = map_input_file(infilename);
	uint32_t *seq = (uint32_t *)inmap.sp;
	uint32_t len = (uint32_t *)inmap.ep - seq;

	if(num_syms == 0) {
		fputs("Finding the largest symbol...", stdout);
		uint32_t highest = 0;
		for(i=0; i<len; i++) {
			if(seq[i] > highest) {
				highest = seq[i];
			}
		}
		num_syms = highest + 1;
		printf(" %d\n", highest);
	}

	uint32_t *out_seq;
	if(mode == MODE_MTF) {
		out_seq = compute_mtf(seq, &len, num_syms);
	}
	else { // DC
		out_seq = compute_dc(seq, &len, num_syms);
	}

	char *outfilename = optind == argc ? NULL : argv[optind];
	FILE *outfile = get_output(infilename, &outfilename, mode);
	printf("Writing to %s...\n", outfilename);
	fwrite(out_seq, sizeof(uint32_t), len, outfile);
	fclose(outfile);

	return 0;
}

uint32_t *compute_mtf(uint32_t *seq, uint32_t *input_len, uint32_t num_syms)
{
	uint32_t i, len = *input_len;
	uint32_t *prev = (uint32_t *)malloc(sizeof(uint32_t) * len);

	puts("Finding links...");
	uint32_t *last = (uint32_t *)malloc(sizeof(uint32_t) * num_syms);
	for(i=0; i<num_syms; i++) {
		last[i] = num_syms - 1 - i;
	}
	for(i=0; i<len; i++) {
		uint32_t c = seq[i];
		prev[i] = last[c];
		last[c] = i + num_syms;
	}

	free(last);
	puts("Count right inversions (RINV[i] = count(S[j] < S[i] where j > i) for i in [0, len-1])...");
	uint32_t *mtf = make_reverse_inversion_vector2(prev, len, len + num_syms);

	free(prev);

	puts("Subtracting...");
	for(i=0; i<len; i++) {
		mtf[i] = num_syms - 1 - mtf[i];
	}

	return mtf;
}

uint32_t *compute_dc(uint32_t *seq, uint32_t *input_len, uint32_t num_syms)
{
	uint32_t i, len = *input_len;
	uint32_t *next = (uint32_t *)malloc(sizeof(uint32_t) * (len + num_syms));

	puts("Finding links...");
	uint32_t *last = (uint32_t *)malloc(sizeof(uint32_t) * num_syms);
	for(i=0; i<num_syms; i++) {
		last[i] = i;
	}
	for(i=0; i<len; i++) {
		uint32_t c = seq[i];
		next[last[c]] = i;
		last[c] = i + num_syms;
	}
	for(i=0; i<num_syms; i++) {
		next[last[i]] = i + len;
	}

	free(last);
	puts("Count right inversions (RINV[i] = count(S[j] < S[i] where j > i) for i in [0, len-1])...");
	uint32_t *inv = make_reverse_inversion_vector(next, len + num_syms);

	uint32_t syms_active = num_syms;
	for(i=0; i<num_syms; i++) {
		if(next[i] > len - 1) {
			inv[i] = (uint32_t)-1;
			syms_active--;
		}
		else {
			inv[i] = next[i];
		}
	}

	puts("Compacting...");
	uint32_t count = num_syms;
	for(i=num_syms; len + num_syms - i - syms_active > 0 && syms_active > 1; i++) {
		if(next[i] > len - 1) {
			inv[count++] = 0;

			syms_active--;
		}
		else if(next[i] + num_syms - i > 1) {
			inv[count++] = inv[i] + 1;
		}
	}

	inv = (uint32_t *)realloc(inv, sizeof(uint32_t) * count);
	*input_len = count;
	return inv;
}

FILE *get_output(char *infilename, char **outfilename, int mode)
{
	static char fnamebuf[256];
	char *fname = *outfilename;
	FILE *outfile;
	if(!fname) {
		fname = fnamebuf;
		fname = stpcpy(fname, infilename);
		stpcpy(fname, (mode == MODE_MTF) ? ".mtf" : ".dc");
		fname = fnamebuf;
		*outfilename = fnamebuf;
	}
	outfile = fopen(fname, "w");
	if(!outfile) {
		perror(fname);
		exit(1);
	}
	return outfile;
}
